# 给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
# 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
# 你可以认为每种硬币的数量是无限的。

from typing import List
import functools


class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        """动态规划"""
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0
        for coin in coins:
            # range从coin开始，避免计算负数下标的情况。
            for x in range(coin, amount + 1):
                dp[x] = min(dp[x], dp[x - coin] + 1)
        return dp[amount] if dp[amount] != float('inf') else -1

    def coinChange_1(self, coins: List[int], amount: int) -> int:
        """使用lru_cache装饰器缓存，直接返回相同参数调用的结果"""

        @functools.lru_cache(amount)
        def dp(rem) -> int:
            if rem < 0:
                return -1
            if rem == 0:
                return 0
            mini = int(1e9)
            for coin in self.coins:
                res = dp(rem - coin)
                if res >= 0 and res < mini:
                    mini = res + 1
            return mini if mini < int(1e9) else -1

        self.coins = coins
        if amount < 1:
            return 0
        return dp(amount)

    def coinChange_error(self, coins: List[int], amount: int) -> int:
        """错误解答"""
        coins.sort(reverse=True)
        ans = 0
        for i in coins:
            ans += amount // i
            amount %= i
        if amount > 0:
            return -1
        return ans


if __name__ == "__main__":
    print(Solution().coinChange(coins=[1, 2, 3], amount=6))
    # print(Solution().coinChange(coins=[2], amount=3))
    # print(Solution().coinChange(coins=[1], amount=0))
    # print(Solution().coinChange(coins=[1], amount=1))
    print(Solution().coinChange(coins=[186, 419, 83, 408], amount=6249))
